Bukti kombinatorial

Contoh

Koefisien xy2 di

( x + y ) 3 = ( x + y ) ( x + y ) ( x + y ) = x x x + x x y + x y x + x y y _ + y x x + y x y _ + y y x _ + y y y = x 3 + 3 x 2 y + 3 x y 2 _ + y 3 . {\displaystyle {\begin{aligned}(x+y)^{3}&=(x+y)(x+y)(x+y)\\&=xxx+xxy+xyx+{\underline {xyy}}+yxx+{\underline {yxy}}+{\underline {yyx}}+yyy\\&=x^{3}+3x^{2}y+{\underline {3xy^{2}}}+y^{3}.\end{aligned}}\,}

sama dengan ( 3 2 ) = 3 {\displaystyle {\binom {3}{2}}=3} kerana ada tiga tali x,y pada panjang 3 dengan tepatnya dua y', digelarkan,

x y y , y x y , y y x , {\displaystyle xyy,\;yxy,\;yyx,}

berkorespon dengan tiga 2-subset elemen pada { 1, 2, 3 }, digelarkan,

{ 2 , 3 } , { 1 , 3 } , { 1 , 2 } , {\displaystyle \{2,3\},\;\{1,3\},\;\{1,2\},}

di mana tiap subset menepatkan kedudukan y dalam suatu tali berkorespon.

Perkara am

Memanjangkan (x + y)n menghasilkan jumlah 2 n produk dari bentuk e1e2 ... e n di mana tiap e i adalah x or y. Mengaturkan semua faktor-faktor menunjukkan bahawa tiap produk sama dengan xn−kyk untuk sesetengah k di antara 0 dan n. Untuk suatu k yang diberikan, yang berikutnya membuktikan sama dengan dalam turutan:

• bilangan salinan xn − kyk dalam pemanjangan
• bilangan ciri-n tali x,y mengadakan y pada tepatnya k berduduk
• bilangan subset elemen-k pada { 1, 2, ..., n}
• ( n k ) {\displaystyle {n \choose k}} (ini adalah sama ada mengikut takrifan, atau suatu perdebatan kepenggabungan jika satu mentakrifkan ( n k ) {\displaystyle {n \choose k}} as n ! k ! ( n − k ) ! {\displaystyle {\frac {n!}{k!\,(n-k)!}}} ).

Ini membuktikan teorem binomial.

Bukti induktif

Induksi menghasilkan suatu lagi bukti pada teorem binomial (1). Apabila n = 0, pada dua belah sama dengan 1, sejak x0 = 1 untuk semua x dan ( 0 0 ) = 1 {\displaystyle {\binom {0}{0}}=1} .Katakan bahawa (1) memegang untuk yang diberikan n; kita kan buktinya untuk n + 1.Untuk j, k ≥ 0, let [ƒ(x, y)] jk menandakan koefisien xjyk dalam polinomial ƒ(x, y).Dengan hipotesis induktif, (x + y)n adalah suatu polinomial di x dan y sepertinya [(x + y)n] jk adalah ( n k ) {\displaystyle {\binom {n}{k}}} if j + k = n, dan 0 kalau tidaknya.Pengenalan

( x + y ) n + 1 = x ( x + y ) n + y ( x + y ) n , {\displaystyle (x+y)^{n+1}=x(x+y)^{n}+y(x+y)^{n},\,}

menunjukkan bahawa (x + y)n+1 juga suatu polinomial pada x dan y, dan

[ ( x + y ) n + 1 ] j k = [ ( x + y ) n ] j − 1 , k + [ ( x + y ) n ] j , k − 1 . {\displaystyle [(x+y)^{n+1}]_{jk}=[(x+y)^{n}]_{j-1,k}+[(x+y)^{n}]_{j,k-1}.\,}

Jika j + k = n + 1, oleh itu (j − 1) + k = n dan j + (k − 1) = n, jadi belah tangan kanan adalah

( n k ) + ( n k − 1 ) = ( n + 1 k ) , {\displaystyle {\binom {n}{k}}+{\binom {n}{k-1}}={\binom {n+1}{k}},}

mengikut pengenalan Pascal. Pada tangan yang lain, jika j +k ≠ n + 1, oleh itu (j – 1) + k ≠ n and j +(k – 1) ≠ n, so we get 0 + 0 = 0. Oleh itu

( x + y ) n + 1 = ∑ k = 0 n + 1 ( n + 1 k ) x n + 1 − k y k , {\displaystyle (x+y)^{n+1}=\sum _{k=0}^{n+1}{\binom {n+1}{k}}x^{n+1-k}y^{k},}

dan menyelesaikan langkah induktif.